package pers.qianyu.month_202011.date_20201123;

/**
 * 416. 分割等和子集
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 * 注释：可以转换为 0 - 1 背包问题
 *
 * @author mizzle rain
 * @date 2020-11-23 20:37
 */
public class CanPartition {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        sum >>= 1;
        boolean[][] dp = new boolean[nums.length + 1][sum + 1];
        for (int i = 0; i < nums.length + 1; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= nums.length; i++) {
            for (int k = 1; k <= sum; k++) {
                if (k < nums[i - 1]) {
                    // 背包装不下
                    dp[i][k] = dp[i - 1][k];
                } else {
                    dp[i][k] = dp[i - 1][k] | dp[i - 1][k - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][sum];
    }

    public static void main(String[] args) {

    }
}
